register allocation

The phase of a {compiler} that determines which values will be

placed in {register}s. Often used to include {register

assignment}. This problem can be shown to be isomorphic to

{graph colouring} by relating values to nodes in the graph and

registers to colours. Values (nodes) which must be valid

simultaneously are linked by edges and cannot be stored in the

same register (coloured the same).

See also {register dancing} and {register spilling}.

Preston Briggs, PhD thesis, Rice University, April 1992:

{"Register Allocation via Graph Coloring"

(ftp://cs.rice.edu/public/preston/thesis.ps)}